The present invention relates to a method and apparatus for handling stored data and particularly, but not exclusively, to memory compaction and garbage collection in real or virtual memory space of a data processing apparatus.
Garbage collection is the automated reclamation of system memory space after its last use by a program. A number of examples of garbage collecting techniques are discussed in "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by R. Jones et al, pub. John Wiley & Sons 1996, ISBN 0-471-94148-4, at pages 1 to 18, and "Uniprocessor Garbage Collection Techniques" by P. R. Wilson, Proceedings of the 1992 International Workshop on Memory Management, St. Malo, France, September 1992. While the storage requirements of many computer programs are simple and predictable, with memory allocation and recovery being handled by the programmer or a compiler, there is a trend toward languages having more complex patterns of execution such that the lifetimes of particular data structures can no longer be determined prior to run-time and hence automated reclamation of this storage, as the program runs, is essential.
One particular class of garbage collection/memory reclamation techniques, as described in the above-mentioned Wilson reference, is mark-sweep collection. In common with many garbage collection techniques it is a two-stage procedure and, as its name suggests, it involves first marking all stored objects that are still reachable by tracing a path or paths through the pointers linking data objects, and then sweeping the memory--that is to say examining every object stored in the memory to determine the unmarked objects whose space may then be reclaimed. In other techniques, such as mark-compact and copying collection, the stored data objects are moved around in memory to form contiguous areas of "live" objects and garbage, with the garbage area being freed for overwriting.
In many cases, garbage collection is a system-wide task which operates on a single global heap, that is to say a single memory area where data structures or objects are stored in no specific order--only with regard to whether a particular space is large enough to hold a particular object. Many languages have no concept of local storage of objects and therefore the global heap will be used for many short-lived data objects, for example those which are local to a single thread. As the same garbage collection or data object sorting techniques are typically applied to this category of data as to longer term data shared between threads, overall collection times may become very long and the load for processing this local data is transferred to the system-wide garbage collection process.